import java.util.ArrayList;
import java.util.List;

public class LeetCode797 {

    public static void main(String[] args) {
        int[][] graph = {{1, 2}, {3}, {3}, {}};

        System.out.println(allPathsSourceTarget(graph));

    }

    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // 从 0 到 n - 1 暴搜
        List<List<Integer>> resultList = new ArrayList<>();
        dfs(resultList, new ArrayList<>(), graph, 0, graph.length);
        return resultList;
    }

    private static void dfs(List<List<Integer>> resultList, List<Integer> result, int[][] graph, int i, int n) {
        if (i == n - 1) {
            result.add(i);
            resultList.add(new ArrayList<>(result));
            result.remove(result.size() - 1);
            return;
        }

        result.add(i);
        for (int next : graph[i]) {
            dfs(resultList, result, graph, next, n);
        }
        // 回溯：这里注意下不要用 remove(i) 或者 remove(Integer.valueOf(i))
        result.remove(result.size() - 1);
    }

}
